# -*- coding: utf-8 -*-
from collections import deque
from model.person import Person
from model.solution import Solution


class GaleShapley:

    def __init__(self, filename):
        self.singles = deque()
        self.men = []
        self.women = dict()

        self.load_data(filename)

    def load_data(self, filename):
        """Loads men and women [O(n)] and their preference lists [O(n)]
        O(n^2)"""
        file = open(filename)
        genre = 'Male'
        for line in file:
            words = line.split(":")
            if line == '\n':
                genre = 'Female'
            else:
                name = words[0]
                preferences = words[1]
                person = Person(name, preferences)
                if genre == 'Male':
                    self.men.append(person)
                else:
                    self.women[name] = person

        file.close()

        self.singles = deque(self.men)

    def match(self):
        """Finds a stable matching in O(n^2)"""
        # If there are still single men
        while len(self.singles) > 0:
            #Take a single man
            m = self.singles.pop()
            #Get next woman's name in the preference list
            name = m.get_prospect()
            if name is None:
                raise Exception("This shouldn't be happening!")
            #Get woman by name
            w = self.women[name]
            #Check who the woman prefers
            if w.prefers(m):
                if w.fiancee is not None:
                    self.singles.appendleft(w.fiancee)
                w.break_up()
                m.engage(w)
            else:
                self.singles.appendleft(m)

    def toString(self):
        str = ''
        for m in self.men:
            str += "(" + m.name + ", " + m.fiancee.name + ")\n"
        return str
